package com.algrithom.recursive;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * 46. 全排列
 */
public class Solution2 {
    
    public static void main(String[] args){
        int[] nums = new int[]{1,2,3};
        Solution2 solution2 = new Solution2();
        List<List<Integer>> result = solution2.permute2(nums);
        result.forEach(System.out::println);
    }
    
    public List<List<Integer>> permute(int[] nums){
        List<List<Integer>> res = new ArrayList<>();
        
        List<Integer> output = new ArrayList<>();
        for (int num : nums) {
            output.add(num);
        }
        
        int n = nums.length;
        backtrack(n,output,res,0);
        return res;
    }
    
    public void backtrack(int n,List<Integer> output,List<List<Integer>> res,int first){
        // 所有数都填完了
        if (first == n) {
            res.add(new ArrayList<>(output));
        }
        for (int i = first; i < n; i++) {
            // 动态维护数组
            Collections.swap(output,first,i);
            // 继续递归填下一个数
            backtrack(n,output,res,first + 1);
            // 撤销操作
            Collections.swap(output,first,i);
        }
    }
    
    public List<List<Integer>> permute2(int[] nums){
        List<List<Integer>> res = new ArrayList<>();
        backtrack(0,res,nums,new ArrayList<>());
        return res;
        
    }
    
    private void backtrack(int index,List<List<Integer>> res,int[] nums,ArrayList<Integer> tmp){
        if (index == nums.length) {
            res.add(new ArrayList<>(tmp));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (tmp.contains(nums[i])) {
                continue;
            }
            tmp.add(nums[i]);
            backtrack(index + 1,res,nums,tmp);
            tmp.remove(tmp.size() - 1);
        }
    }
    private void backtrack(List<List<Integer>> res, int[] nums, ArrayList<Integer> tmp) {
        if (tmp.size() == nums.length) {
            res.add(new ArrayList<>(tmp));
            return;
        }
        for (int num : nums) {
            if (tmp.contains(num)) {
                continue;
            }
            tmp.add(num);
            backtrack(res, nums, tmp);
            tmp.remove(tmp.size() - 1);
        }
    }
}
